Activity Selection

The Activity Selection problem is a classic example of a greedy algorithm application. It is concerned with selecting the maximum number of activities that don't overlap in time from a given set of activities.

Problem Statement

Given n activities with their start and finish times, select the maximum number of activities that a single person can attend without any overlap. Each activity is represented by a start time s[i] and a finish time f[i].

Greedy Strategy

The optimal greedy strategy for the activity selection problem involves selecting activities based on their finishing times. Here are the steps:

1. Sort the activities based on their finish times.
2. Select the first activity from the sorted list and add it to the result as it finishes the earliest.
3. Iterate through the remaining activities and select the next activity if its start time is greater than or equal to the finish time of the last selected activity.

Algorithm

1. Sort all the activities by their finishing time.
2. Initialize lastSelectedFinishTime to 0 (or negative infinity if using time).
3. Initialize selectedActivities to an empty list.
4. For each activity in the sorted list:
   • If the start time of the activity is greater than or equal to lastSelectedFinishTime:
     • Add the activity to selectedActivities.
     • Update lastSelectedFinishTime to the finish time of the current activity.
5. Return selectedActivities as the list of chosen activities.

Greedy-Activity-Selector(A, s, f):
	Sort A by finish times stored in f
	S = {A[1]}  # Select the first activity
	k = 1
	for i = 2 to n:
	    if s[i] >= f[k]:
	        S = S U {A[i]}  # Select the activity
	        k = i
	return S

Complexity

• Time Complexity: $O (n \log n)$ due to the sorting step, followed by an $O (n)$ pass to select activities.
• Space Complexity: $O (1)$, not counting the space needed for output; this is due to the inplace sorting and a constant number of extra variables.

Example of the Activity Selection Problem

Suppose we have the following set of activities (labeled from A to E) with their respective start and finish times:

Activity	Start Time	Finish Time
A	1	4
B	3	5
C	0	6
D	5	7
E	8	9

Applying the Greedy Algorithm

1. Step 1: Sort Activities by Finish Time

   • Sorted order of activities based on their finish times: A, B, D, E, C

2. Step 2: Select Activities

   • Start with the first activity in the sorted list.
   • Activity A (1, 4)
   • Next, we skip B because it overlaps with A (it starts before A finishes).
   • The next activity that doesn't overlap with A is D (5, 7), so we select it.
   • Finally, activity E (8, 9) does not overlap with D and can be selected.

Selected Activities

• A (Starts at 1, finishes at 4)
• D (Starts at 5, finishes at 7)
• E (Starts at 8, finishes at 9)

These activities are chosen because they allow for the maximum number of non-overlapping activities (three in this case). If you choose any activity like C that spans a long duration (0, 6), it would block out multiple other shorter activities, thus reducing the overall count.

Proof of Optimality

Step 1: Definition of Sets

• Let $A$ be the set of activities selected by the greedy algorithm.
• Let $B$ be any other set of activities that also do not overlap.

Step 2: Assumptions

• The greedy algorithm selects activities based on the earliest finishing times.
• Assume that activities in both $A$ and $B$ are sorted by their finish times. Let $a_1, a_2, \ldots, a_k$ be the activities in $A$ and $b_1, b_2, \ldots, b_m$ be the activities in $B$, where $f (a_i)$ and $f (b_i)$ denote their respective finish times.

Step 3: Method of Substitution

• The goal is to show that the number of activities in $A$ (|A|) is at least as large as the number of activities in $B$ (|B|), i.e., $|A| \geq |B|$.

Step 4: Proof by Induction

1. Base Case: Compare $a_1$ and $b_1$. Since $a_1$ is selected by the greedy algorithm, it has the earliest finish time among all activities and thus $f (a_1) \leq f (b_1)$.
2. Inductive Step:
   • Assume that for the first $j$ activities in $B$, they can be replaced by activities in $A$ such that $f (a_i) \leq f (b_i)$ for all $i \leq j$.
   • Consider the next activity $b_{j+1}$. Since $b_{j+1}$ does not overlap with $b_j$, we have $s (b_{j+1}) \geq f (b_j)$.
   • From the greedy selection, $a_{j+1}$ is the next activity selected after $a_j$ with $f (a_j) \leq f (b_j)$, and thus $s (a_{j+1}) \geq f (a_j)$. Therefore, $f (a_{j+1})$ must also be less than or equal to $f (b_{j+1})$ because $a_{j+1}$ is the earliest finishing activity available after $a_j$.

Step 5: Conclusion

• By induction, each activity in $B$ can be matched with an activity in $A$ that finishes no later than itself, which implies $|A| \geq |B|$.
• Since $B$ was any arbitrary set of non-overlapping activities, $A$ must be the largest possible set of non-overlapping activities.
• Therefore, the set $A$ selected by the greedy algorithm is optimal.